package LeetCode._02_数组;

public class _53_最大子数组和 {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        return maxSubArray(nums,0,nums.length);
    }


    //函数定义：计算范围[begin,end)的最大子数组和
    int maxSubArray(int[] nums,int begin,int end){
        if(end - begin < 2) return nums[begin]; //base case

        int mid = (begin + end) >> 1; //均匀分割

        //计算特殊情况，在[begin,mid) 和 [mid,end)之间
        int leftMax = nums[mid - 1];
        int leftSum = leftMax;
        for(int i=mid-2;i>=begin;i--){
            leftSum += nums[i];
            leftMax = Math.max(leftMax,leftSum);
        }

        int rightMax = nums[mid];
        int rightSum = rightMax;
        for(int i=mid+1;i<end;++i){
            rightSum += nums[i];
            rightMax = Math.max(rightMax,rightSum);
        }

        //递归去计算
        return Math.max(leftMax+rightMax,
                Math.max(maxSubArray(nums,begin,mid),maxSubArray(nums,mid,end)));
    }
}
